//丢失的数字
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int xorVal = 0;
        for(size_t i = 0 ; i < nums.size() ; ++i)
        {
            xorVal ^= (nums[i]^i);
        }
        xorVal^= nums.size();
        return xorVal;
    }
};

//两整数之和
class Solution {
public:
    int getSum(int a, int b) {
        int temp = 0;
        while(b)
        {
            temp = a;
            a ^= b;
            b = ((temp&b) << 1);
        }
        return a;
    }
};

//只出现一次的数字II
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for(size_t i = 0 ; i < 32 ; ++i)
        {
            int bitSum = 0;
            for(auto& x : nums)
            {
                if((x>>i)&1)
                {
                    bitSum++;
                }
            }
            if(bitSum % 3 == 1) ret |= (1 << i);
        }
        return ret;
    }
};

//只出现一次的数字III
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int val = 0;
        //a和b就是只出现一次的数字
        //异或原数组，通过消消乐，最终结果一定是a^b
        for(auto& x : nums)
        {
            val ^= x;
        }
        //a^b的比特位为1的情况分成两组
        int i = 0;
        for(;i < 32 ; ++i)
        {
            if(((val>>i)&1) == 1) break;
        }
        int ret1 = 0 , ret2 = 0;
        for(auto& x : nums)
        {
            if((x >> i)&1) ret1 ^= x;
            else ret2 ^= x;
        }
        return {ret1,ret2};
    }
};

//消失的两个数字
class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        //通过位运算算出a^b
        int n = nums.size();
        int val = 0;
        for(size_t i = 0 ; i <= n+2 ; ++i)
        {
            if(i < n)val ^= nums[i];
            if(i >= 1)val ^= i;
        }
        //找出为1的比特位的位置，分组讨论
        size_t i = 0;
        for(; i < 32 ; ++i)
        {
            if((val >> i) & 1) break;
        }
        //分组后，问题转化为丢失的数字
        int ret1 = 0 , ret2 = 0;
        for(auto& x : nums)
        {
            if((x >> i) & 1)ret1 ^= x;
            else ret2 ^= x;
        }
        for(size_t j = 1 ; j <= n+2 ; j++)
        {
            if((j >> i) & 1)ret1 ^= j;
            else ret2 ^= j;
            
        }
        return {ret1,ret2};
    }
};









